package leetcode101.binary_search;

/**
 * @author Synhard
 * @version 1.0
 * @Class Code2
 * @Description 34. Find First and Last Position of Element in Sorted Array
 *
 * Given an array of integers nums sorted in ascending order,
 * find the starting and ending position of a given target value.
 *
 * If target is not found in the array, return [-1, -1].
 *
 * Follow up: Could you write an algorithm with O(log n) runtime complexity?
 *
 * Example 1:
 *
 * Input: nums = [5,7,7,8,8,10], target = 8
 * Output: [3,4]
 * Example 2:
 *
 * Input: nums = [5,7,7,8,8,10], target = 6
 * Output: [-1,-1]
 * Example 3:
 *
 * Input: nums = [], target = 0
 * Output: [-1,-1]
 *  
 *
 * Constraints:
 *
 * 0 <= nums.length <= 105
 * -109 <= nums[i] <= 109
 * nums is a non-decreasing array.
 * -109 <= target <= 109
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-03-28 9:56
 */
public class Code2 {
    public static void main(String[] args) {
        int[] nums = new int[]{2, 2};
        searchRange(nums, 2);
    }
    public static int[] searchRange(int[] nums, int target) {
        int low = 0, high = nums.length - 1, mid = 0, lEdge = 0, rEdge = 0;

        while (low <= high) {
            mid = (low + high) >> 1;
            if (nums[mid] == target) {
                lEdge = leftEdge(nums, mid, target);
                rEdge = rightEdge(nums, mid, target);
                return new int[]{lEdge, rEdge};
            }
            if (nums[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return new int[]{-1, -1};
    }

    // 返回目标值从posi开始往左边的边界，如果无的话返回posi
    public static int leftEdge(int[] nums, int posi, int target) {
        for (int i = posi; i > -1; i--) {
            if (nums[i] != target) {
                return i + 1;
            }
        }
        return 0;
    }
    // 返回目标值从posi开始往右边的边界，如果无的话返回posi
    public static int rightEdge(int[] nums, int posi, int target) {
        for (int i = posi; i < nums.length; i++) {
            if (nums[i] != target) {
                return i - 1;
            }
        }
        return nums.length - 1;
    }
}
/*
思路就是使用二分查找定位到第一个是目标值的元素
然后定义两个搜索函数分别搜索第一个目标值左边元素的下界
和第一个目标值右边元素的上界
 */